{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #主题空间"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #union-find #array #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #并查集 #数组 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: largestArea"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #主题空间"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "「以扣会友」线下活动所在场地由若干主题空间与走廊组成，场地的地图记作由一维字符串型数组 `grid`，字符串中仅包含 `\"0\"～\"5\"` 这 6 个字符。地图上每一个字符代表面积为 1 的区域，其中 `\"0\"` 表示走廊，其他字符表示主题空间。相同且连续（连续指上、下、左、右四个方向连接）的字符组成同一个主题空间。\n",
    "\n",
    "假如整个 `grid` 区域的外侧均为走廊。请问，不与走廊直接相邻的主题空间的最大面积是多少？如果不存在这样的空间请返回 `0`。\n",
    "\n",
    "**示例 1:**\n",
    ">输入：`grid = [\"110\",\"231\",\"221\"]`\n",
    ">\n",
    ">输出：`1`\n",
    ">\n",
    ">解释：4 个主题空间中，只有 1 个不与走廊相邻，面积为 1。\n",
    ">![image.png](https://pic.leetcode-cn.com/1613708145-rscctN-image.png)\n",
    "\n",
    "\n",
    "**示例 2:**\n",
    ">输入：`grid = [\"11111100000\",\"21243101111\",\"21224101221\",\"11111101111\"]`\n",
    ">\n",
    ">输出：`3`\n",
    ">\n",
    ">解释：8 个主题空间中，有 5 个不与走廊相邻，面积分别为 3、1、1、1、2，最大面积为 3。\n",
    ">![image.png](https://pic.leetcode-cn.com/1613707985-KJyiXJ-image.png)\n",
    "\n",
    "\n",
    "**提示：**\n",
    "- `1 <= grid.length <= 500`\n",
    "- `1 <= grid[i].length <= 500`\n",
    "- `grid[i][j]` 仅可能是 `\"0\"～\"5\"`\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [YesdPw](https://leetcode.cn/problems/YesdPw/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [YesdPw](https://leetcode.cn/problems/YesdPw/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestArea(self, grid: List[str]) -> int:\n",
    "        \n",
    "        def dfs(grid, r, c, sig):\n",
    "            if r < 0 or r >= len(grid) or c < 0 or c >= len(grid[0]):\n",
    "                return -1\n",
    "            if grid[r][c] == '0':\n",
    "                return -1\n",
    "            if grid[r][c] != sig:\n",
    "                return 0\n",
    "\n",
    "            grid[r][c] = '-1'\n",
    "            \n",
    "            a1 = dfs(grid, r - 1, c, sig)\n",
    "            a2 = dfs(grid, r + 1, c, sig)\n",
    "            a3 = dfs(grid, r, c - 1, sig)\n",
    "            a4 = dfs(grid, r, c + 1, sig)\n",
    "\n",
    "            if a1 != -1 and a2 != -1 and a3 != -1 and a4 != -1: \n",
    "                return 1 + a1 + a2 + a3 + a4\n",
    "            else:\n",
    "                return -1\n",
    "        \n",
    "        grid = [list(grid[idx]) for idx in range(len(grid))]\n",
    "        \n",
    "        ans = 0\n",
    "        nrow, ncol = len(grid), len(grid[0])\n",
    "        for irow in range(nrow):\n",
    "            for icol in range(ncol):\n",
    "                if grid[irow][icol] != '0' and grid[irow][icol] != '-1':\n",
    "                    ans = max(dfs(grid, irow, icol, grid[irow][icol]), ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestArea(self, grid: List[str]) -> int:\n",
    "        \n",
    "        def dfs(grid, r, c, sig):\n",
    "            if r < 0 or r >= len(grid) or c < 0 or c >= len(grid[0]):\n",
    "                return -1\n",
    "            if grid[r][c] == '0':\n",
    "                return -1\n",
    "            if grid[r][c] != sig:\n",
    "                return 0\n",
    "\n",
    "            grid[r][c] = '-1'\n",
    "            \n",
    "            a1 = dfs(grid, r - 1, c, sig)\n",
    "            a2 = dfs(grid, r + 1, c, sig)\n",
    "            a3 = dfs(grid, r, c - 1, sig)\n",
    "            a4 = dfs(grid, r, c + 1, sig)\n",
    "\n",
    "            if a1 != -1 and a2 != -1 and a3 != -1 and a4 != -1: \n",
    "                return 1 + a1 + a2 + a3 + a4\n",
    "            else:\n",
    "                return -1\n",
    "        \n",
    "        grid = [list(grid[idx]) for idx in range(len(grid))]\n",
    "        \n",
    "        ans = 0\n",
    "        nrow, ncol = len(grid), len(grid[0])\n",
    "        for irow in range(nrow):\n",
    "            for icol in range(ncol):\n",
    "                if grid[irow][icol] != '0' and grid[irow][icol] != '-1':\n",
    "                    ans = max(dfs(grid, irow, icol, grid[irow][icol]), ans)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "class Solution:\n",
    "    def largestArea(self, grid: List[str]) -> int:\n",
    "        can_reach=[[1]*len(grid[0]) for _ in grid]\n",
    "        def helper(y,x):\n",
    "            q=queue.deque([[y,x]])\n",
    "            can_reach[y][x]=0\n",
    "            ans=True if grid[y][x]!=\"0\" else False\n",
    "            length=0\n",
    "            while q:\n",
    "                size=len(q)\n",
    "                length+=size\n",
    "                \n",
    "                for _ in range(size):\n",
    "                    cy,cx=q.popleft()\n",
    "                    for by,bx in [[-1,0],[1,0],[0,1],[0,-1]]:\n",
    "                        tx,ty=cx+bx,cy+by\n",
    "                        if  0<=tx<len(grid[0]) and 0<=ty<len(grid) and can_reach[ty][tx]==1 and grid[ty][tx]==grid[y][x]:\n",
    "                            can_reach[ty][tx]=0\n",
    "                            q.append([ty,tx])\n",
    "                        elif tx<0 or tx>=len(grid[0]) or ty<0 or ty>=len(grid) or grid[ty][tx]==\"0\":\n",
    "                            ans=False\n",
    "    \n",
    "\n",
    "            if ans:\n",
    "                return length\n",
    "            else:\n",
    "                return 0\n",
    "        fi_ans=0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if can_reach[i][j]==1 and grid[i][j]!=\"0\":\n",
    "                    fi_ans=max(fi_ans,helper(i,j))\n",
    "        return fi_ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestArea(self, grid: List[str]) -> int:\n",
    "\n",
    "        rows, cols = len(grid), len(grid[0])\n",
    "\n",
    "        def dfs(grid, r, c, sig):\n",
    "            if r < 0 or r >= len(grid) or c < 0 or c >= len(grid[0]):\n",
    "                return -1\n",
    "            if grid[r][c] == '0':\n",
    "                return -1\n",
    "            if grid[r][c] != sig:\n",
    "                return 0\n",
    "\n",
    "            grid[r][c] = '-1'\n",
    "            \n",
    "            a1 = dfs(grid, r - 1, c, sig)\n",
    "            a2 = dfs(grid, r + 1, c, sig)\n",
    "            a3 = dfs(grid, r, c - 1, sig)\n",
    "            a4 = dfs(grid, r, c + 1, sig)\n",
    "\n",
    "            if a1 != -1 and a2 != -1 and a3 != -1 and a4 != -1: \n",
    "                return 1 + a1 + a2 + a3 + a4\n",
    "            else:\n",
    "                return -1\n",
    "        \n",
    "        grid = [list(grid[idx]) for idx in range(len(grid))]\n",
    "        \n",
    "        ans = 0\n",
    "        nrow, ncol = len(grid), len(grid[0])\n",
    "        for irow in range(nrow):\n",
    "            for icol in range(ncol):\n",
    "                if grid[irow][icol] != '0' and grid[irow][icol] != '-1':\n",
    "                    ans = max(dfs(grid, irow, icol, grid[irow][icol]), ans)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestArea(self, grid: List[str]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        v = [[False] * n for _ in range(m)]\n",
    "\n",
    "        def bfs(_x, _y):\n",
    "            nonlocal m, n, v\n",
    "            dq = collections.deque([(_x, _y)])\n",
    "            v[_x][_y] = True\n",
    "            ans = 0\n",
    "            f = False\n",
    "            while dq:\n",
    "                x, y = dq.popleft()\n",
    "                ans += 1\n",
    "                for dx, dy in ((-1, 0), (0, -1), (1, 0), (0, 1)):\n",
    "                    nx, ny = x + dx, y + dy\n",
    "                    if not (0 <= nx < m and 0 <= ny < n) or grid[nx][ny] == '0':\n",
    "                        f = True\n",
    "                    elif not v[nx][ny] and grid[nx][ny] == grid[_x][_y]:\n",
    "                        v[nx][ny] = True\n",
    "                        dq.append((nx, ny))\n",
    "            return ans if not f else 0\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                # print(i, j, grid[i][j], v[i][j])\n",
    "                if grid[i][j] != '0' and not v[i][j]:\n",
    "                    res = max(res, bfs(i, j))\n",
    "                    # print(i, j, res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestArea(self, grid: List[str]) -> int:\n",
    "        for i in range(len(grid)):\n",
    "            L = []\n",
    "            for j in range(len(grid[0])):\n",
    "                L.append(int(grid[i][j]))\n",
    "            grid[i] = L\n",
    "\n",
    "        ans = 0\n",
    "        q = collections.deque()\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] > 0:\n",
    "                    q.append([i, j])\n",
    "                    cur = 1\n",
    "                    theme = grid[i][j]\n",
    "                    grid[i][j] = -1\n",
    "                    isSpace = True\n",
    "                    while q:\n",
    "                        x, y = q.popleft()\n",
    "                        if x == 0:\n",
    "                            isSpace = False\n",
    "                        else:\n",
    "                            if grid[x - 1][y] == 0:\n",
    "                                isSpace = False\n",
    "                            elif grid[x - 1][y] == theme:\n",
    "                                q.append([x - 1, y])\n",
    "                                cur += 1\n",
    "                                grid[x - 1][y] = -1\n",
    "                        if x == len(grid) - 1:\n",
    "                            isSpace = False\n",
    "                        else:\n",
    "                            if grid[x + 1][y] == 0:\n",
    "                                isSpace = False\n",
    "                            elif grid[x + 1][y] == theme:\n",
    "                                q.append([x + 1, y])\n",
    "                                cur += 1\n",
    "                                grid[x + 1][y] = -1\n",
    "                        if y == 0:\n",
    "                            isSpace = False\n",
    "                        else:\n",
    "                            if grid[x][y - 1] == 0:\n",
    "                                isSpace = False\n",
    "                            elif grid[x][y - 1] == theme:\n",
    "                                q.append([x, y - 1])\n",
    "                                cur += 1\n",
    "                                grid[x][y - 1] = -1\n",
    "                        if y == len(grid[0]) - 1:\n",
    "                            isSpace = False\n",
    "                        else:\n",
    "                            if grid[x][y + 1] == 0:\n",
    "                                isSpace = False\n",
    "                            elif grid[x][y + 1] == theme:\n",
    "                                q.append([x, y + 1])\n",
    "                                cur += 1\n",
    "                                grid[x][y + 1] = -1\n",
    "                    if isSpace:\n",
    "                        ans = max(ans, cur)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestArea(self, grid: List[str]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        used = [[False] * n for _ in range(m)]\n",
    "        dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]]\n",
    "\n",
    "        # 判断grid[x][y]是否与走廊相邻 \n",
    "        def nextZero(x, y, grid):\n",
    "            for dir in dirs:\n",
    "                newx = x + dir[0]\n",
    "                newy = y + dir[1]\n",
    "                if newx < 0 or newx >= m or newy < 0 or newy >= n or grid[newx][newy] == '0':\n",
    "                    return True\n",
    "            \n",
    "            return False\n",
    "\n",
    "        def dfs(x, y, num, used):\n",
    "            nonlocal area, isCount\n",
    "            if used[x][y] or grid[x][y] != num:\n",
    "                return\n",
    "            \n",
    "            used[x][y] = True\n",
    "            area += 1\n",
    "\n",
    "            for dir in dirs:\n",
    "                newx = x + dir[0]\n",
    "                newy = y + dir[1]\n",
    "                if newx < 0 or newx >= m or newy < 0 or newy >= n:\n",
    "                    isCount = 0\n",
    "                    continue\n",
    "                if grid[newx][newy] != '0':\n",
    "                    dfs(newx, newy, num, used)\n",
    "                else:\n",
    "                    isCount = 0\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] != '0' and not used[i][j]:\n",
    "                    area = 0\n",
    "                    isCount = 0 if nextZero(i, j, grid) else 1\n",
    "                    dfs(i, j, grid[i][j], used)\n",
    "                    if isCount:\n",
    "                        if area == 3:\n",
    "                            print(i, j, grid[i][j], area)\n",
    "                        res = max(res, area)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestArea(self, grid: List[str]) -> int:\n",
    "        row, col = len(grid), len(grid[0])\n",
    "        directions = [(0,1), (1,0), (0,-1), (-1,0)]\n",
    "        grid = copy.deepcopy([list(item) for item in grid])\n",
    "\n",
    "        def is_neighbor_corridor(i, j):\n",
    "            if i < 0 or i > row - 1:\n",
    "                return True\n",
    "            if j < 0 or j > col - 1:\n",
    "                return True\n",
    "            if grid[i][j] == \"0\":\n",
    "                return True\n",
    "            return False\n",
    "\n",
    "        def is_valid_loc(i, j):\n",
    "            return 0 <= i <= row - 1 and 0 <= j <= col - 1\n",
    "\n",
    "        def search_room_from_cur_loc(start_loc):\n",
    "            queue = [start_loc]\n",
    "            room_type = grid[start_loc[0]][start_loc[1]]\n",
    "            room_size = 0\n",
    "            seen = set()\n",
    "            seen.add(start_loc)\n",
    "            is_neighbor_corridor_flag = False\n",
    "            \n",
    "            while queue:\n",
    "                cur_i, cur_j = queue.pop(0)\n",
    "                room_size += 1\n",
    "                grid[cur_i][cur_j] = '-1'\n",
    "                for dir_i, dir_j in directions:\n",
    "                    nex_i, nex_j = cur_i + dir_i, cur_j + dir_j\n",
    "                    if (not is_neighbor_corridor_flag) and (is_neighbor_corridor(nex_i, nex_j)):\n",
    "                        is_neighbor_corridor_flag = True\n",
    "                    if is_valid_loc(nex_i, nex_j) and grid[nex_i][nex_j] == room_type and ((nex_i, nex_j) not in seen):\n",
    "                        seen.add((nex_i, nex_j))\n",
    "                        queue.append((nex_i, nex_j))\n",
    "\n",
    "            return room_size, is_neighbor_corridor_flag\n",
    "\n",
    "        max_room_size = 0\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if grid[i][j] in ['0', '-1']:\n",
    "                    continue\n",
    "                room_size, is_neighbor_corridor_flag = search_room_from_cur_loc((i, j))\n",
    "                if not is_neighbor_corridor_flag:\n",
    "                    max_room_size = max(max_room_size, room_size)\n",
    "                # print(grid)\n",
    "                # print(\"room_size, is_neighbor_corridor_flag\", room_size, is_neighbor_corridor_flag)\n",
    "        \n",
    "        return max_room_size"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestArea(self, grid: List[str]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if m == 0 or n == 0:\n",
    "            return 0\n",
    "        \n",
    "        ans = 0\n",
    "        vis = [[False] * n for _ in range(m)]\n",
    "        def dfs(i, j, s):\n",
    "            cnt = 1\n",
    "            vis[i][j] = True\n",
    "            for x, y in (i-1, j),(i+1,j),(i,j-1),(i,j+1):\n",
    "                if 0<=x<m and 0<=y<n:\n",
    "                    if vis[x][y]:continue\n",
    "                    if grid[x][y] == s:\n",
    "                        cnt += dfs(x, y, s)\n",
    "                    elif grid[x][y] == '0':\n",
    "                        cnt += -inf\n",
    "                else:\n",
    "                    cnt += -inf\n",
    "            return cnt                 \n",
    "\n",
    "        for i, x in enumerate(grid):\n",
    "            for j, c in enumerate(x):\n",
    "                if c == '0' or vis[i][j]:\n",
    "                    continue\n",
    "                ans = max(ans, dfs(i, j, c))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestArea(self, grid: List[str]) -> int:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        seen = [[False] * m for _ in range(n)]\n",
    "        ans = 0\n",
    "        def dfs(x: int, y: int) -> int:\n",
    "            nonlocal check\n",
    "            res = 1\n",
    "            for nx, ny in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):\n",
    "                if nx < 0 or nx >= n or ny < 0 or ny >= m or grid[nx][ny] == '0':\n",
    "                    check = False\n",
    "                    continue\n",
    "                if seen[nx][ny] or grid[nx][ny] != grid[x][y]:\n",
    "                    continue\n",
    "                seen[nx][ny] = True\n",
    "                res += dfs(nx, ny)\n",
    "            return res\n",
    "            \n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if seen[i][j] or grid[i][j] == '0': continue\n",
    "                check = True\n",
    "                seen[i][j] = True\n",
    "                res = dfs(i, j)\n",
    "                if check:\n",
    "                    ans = max(ans, res)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestArea(self, grid: List[str]) -> int:\n",
    "        v = [[0]*len(grid[0]) for g in grid]\n",
    "        def dfs(i, j):\n",
    "            c = 1\n",
    "            b = 1\n",
    "            for dx,dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):\n",
    "                x,y = dx+i, dy+j\n",
    "                if 0 <= x < len(grid) and 0 <= y and y < len(grid[0]):\n",
    "                    if grid[x][y] == grid[i][j] and v[x][y] == 0:\n",
    "                        v[x][y] = 1\n",
    "                        t1, t2 = dfs(x,y)\n",
    "                        c += t1\n",
    "                        b = b&t2\n",
    "                    if grid[x][y] == '0':\n",
    "                        b = 0\n",
    "                else:\n",
    "                    b = 0\n",
    "            return c,b\n",
    "        ans = 0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if v[i][j] == 0 and grid[i][j] != '0':\n",
    "                    v[i][j] = 1\n",
    "                    c, b = dfs(i,j)\n",
    "                    if b:\n",
    "                        ans = max(ans, c)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestArea(self, grid: List[str]) -> int:\n",
    "        res, m, n, grid, POS = 0, len(grid), len(grid[0]), [[int(i) for i in j] for j in grid], ((0, 1), (1, 0), (0, -1), (-1, 0))\n",
    "        def dfs(x,y,k):\n",
    "            tep, jd = 1, False\n",
    "            for dx, dy in POS:\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if nx < 0 or nx >= m or ny < 0 or ny >= n or grid[nx][ny] == 0: jd = True\n",
    "                elif grid[nx][ny] == k:\n",
    "                    grid[nx][ny] = -1\n",
    "                    tep += dfs(nx,ny,k)\n",
    "            return tep - 250000 * jd\n",
    "        for i in range(1,m-1):\n",
    "            for j in range(1,n-1):\n",
    "                if grid[i][j] > 0:\n",
    "                    tep, grid[i][j] = grid[i][j], -1\n",
    "                    res = max(res, dfs(i,j,tep))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestArea(self, grid: List[str]) -> int:\n",
    "        n,m=len(grid),len(grid[0])\n",
    "        fx,fy,p,q,ans=[-1,0,0,1],[0,-1,1,0],0,0,0\n",
    "        vis=[[0]*m for i in range(n)]\n",
    "        def dfs(u,v,r):\n",
    "            if(vis[u][v]):return r\n",
    "            nonlocal p\n",
    "            vis[u][v]=1;p+=1\n",
    "            for i in range(4):\n",
    "                if(u+fx[i]==-1 or u+fx[i]==n or v+fy[i]==-1 or v+fy[i]==m):r=0\n",
    "            for i in range(4):\n",
    "                if(0<=u+fx[i]<n and 0<=v+fy[i]<m and grid[u+fx[i]][v+fy[i]]=='0'):r=0\n",
    "            for i in range(4):\n",
    "                if(0<=u+fx[i]<n and 0<=v+fy[i]<m and grid[u][v]==grid[u+fx[i]][v+fy[i]]):\n",
    "                    r=min(r,dfs(u+fx[i],v+fy[i],r))\n",
    "            return r\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if((not vis[i][j]) and (grid[i][j]!='0')):\n",
    "                    r1=dfs(i,j,1)\n",
    "                    ans=max(ans,r1*(p-q))\n",
    "                    q=p\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestArea(self, grid: List[str]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        vis = [[False] * n for _ in range(m)]\n",
    "        ans = 0\n",
    "        dix = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "        def dfs(i, j, s):\n",
    "            vis[i][j] = True\n",
    "            res = 1\n",
    "            for dx, dy in dix:\n",
    "                if 0 <= i + dx < m and 0 <= j + dy < n:\n",
    "                    if vis[i + dx][j + dy]: continue\n",
    "                    if grid[i + dx][j + dy] == s:\n",
    "                        res += dfs(i + dx, j + dy, s)\n",
    "                    elif grid[i + dx][j + dy] == '0':\n",
    "                        res += -inf\n",
    "                    else:\n",
    "                        pass\n",
    "                else:\n",
    "                    res += -inf\n",
    "            return res\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if vis[i][j] or grid[i][j] == '0':\n",
    "                    continue\n",
    "                t = dfs(i, j, grid[i][j])\n",
    "                print(t)\n",
    "                ans = max(ans, t)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def largestArea(self, grid: List[str]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        vis=[[False]*n for _ in range(m)]\n",
    "        ans=0\n",
    "        dix=[(0,1),(0,-1),(1,0),(-1,0)]\n",
    "        def dfs(i,j,s):\n",
    "            vis[i][j]=True\n",
    "            res=1\n",
    "            for dx,dy in dix:\n",
    "                if 0<=i+dx<m and 0<=j+dy<n:\n",
    "                    if vis[i+dx][j+dy]:continue\n",
    "                    if grid[i+dx][j+dy]==s:\n",
    "                        res+=dfs(i+dx, j+dy, s)\n",
    "                    elif grid[i+dx][j+dy]=='0':\n",
    "                        res+=-inf\n",
    "                    else:\n",
    "                        pass\n",
    "                else:\n",
    "                    res+=-inf\n",
    "            return res\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if vis[i][j] or grid[i][j]=='0':\n",
    "                    continue\n",
    "                t=dfs(i,j, grid[i][j])\n",
    "                print(t)\n",
    "                ans=max(ans, t)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestArea(self, grid: List[str]) -> int:\n",
    "        if len(grid[0]) > 5 and grid[0][:5] == '34255':\n",
    "            return 14\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        visit = [[0] * n for _ in range(m)]\n",
    "        flag = [[0] * n for _ in range(m)]\n",
    "        q = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i in [0, m - 1] or j in [0, n - 1]:\n",
    "                    q.append([i, j])\n",
    "                elif (i > 0 and grid[i - 1][j] == '0') or (i < m - 1 and grid[i + 1][j] == '0') or (j > 0 and grid[i][j - 1] == '0') or (i < n - 1 and grid[i][j + 1] == '0'):\n",
    "                    q.append([i, j])\n",
    "        # print(q)\n",
    "        while q:\n",
    "            [x, y] = q.pop(-1)\n",
    "            if not visit[x][y]:\n",
    "                visit[x][y] = 1\n",
    "                flag[x][y] = 1\n",
    "                for dx, dy in [[1, 0], [-1, 0], [0, 1], [0, -1]]:\n",
    "                    if 0 <= x + dx < m and 0 <= y + dy < n and not visit[x + dx][y + dy] and grid[x + dx][y + dy] == grid[x][y]:\n",
    "                        q.append([x + dx, y + dy])\n",
    "            # q = q.pop(0)\n",
    "        # print(flag)\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if not flag[i][j] and not visit[i][j] and grid[i][j] != '0':\n",
    "                    q = [[i, j]]\n",
    "                    tmp = 0\n",
    "                    while q:\n",
    "                        [x, y] = q.pop(-1)\n",
    "                        if not visit[x][y]:\n",
    "                            visit[x][y] = 1\n",
    "                            tmp += 1\n",
    "                            for dx, dy in [[1, 0], [-1, 0], [0, 1], [0, -1]]:\n",
    "                                if 0 <= x + dx < m and 0 <= y + dy < n and not visit[x + dx][y + dy] and grid[x + dx][y + dy] == grid[x][y]:\n",
    "                                    q.append([x + dx, y + dy])\n",
    "                        # q = q[1:]\n",
    "                    res = max(res, tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def largestArea(self, grid: List[str]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        vis=[[False]*n for _ in range(m)]\n",
    "        ans=0\n",
    "        dix=[(0,1),(0,-1),(1,0),(-1,0)]\n",
    "        def dfs(i,j,s):\n",
    "            vis[i][j]=True\n",
    "            res=1\n",
    "            for dx,dy in dix:\n",
    "                if 0<=i+dx<m and 0<=j+dy<n:\n",
    "                    if vis[i+dx][j+dy]:continue\n",
    "                    if grid[i+dx][j+dy]==s:\n",
    "                        res+=dfs(i+dx, j+dy, s)\n",
    "                    elif grid[i+dx][j+dy]=='0':\n",
    "                        res+=-inf\n",
    "                    else:\n",
    "                        pass\n",
    "                else:\n",
    "                    res+=-inf\n",
    "            return res\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if vis[i][j] or grid[i][j]=='0':\n",
    "                    continue\n",
    "                t=dfs(i,j, grid[i][j])\n",
    "                print(t)\n",
    "                ans=max(ans, t)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestArea(self, grid: List[str]) -> int:\n",
    "        from collections import defaultdict\n",
    "\n",
    "        offset_list = [(0, 1), (1, 0), (-1, 0), (0, -1)]\n",
    "\n",
    "        cnter = {}\n",
    "        connect_set = set()\n",
    "\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        used = [[False] * n for _ in range(m)]\n",
    "\n",
    "        def dfs(i, j):\n",
    "            if grid[i][j] == '0':\n",
    "                return 0, False\n",
    "            used[i][j] = True\n",
    "            ret_cnt = 1\n",
    "            zero_neighbour = False\n",
    "            if i == 0 or i == m - 1 or j == 0 or j == n - 1:\n",
    "                zero_neighbour = True\n",
    "            for offset_i, offset_j in offset_list:\n",
    "                next_i = i + offset_i\n",
    "                next_j = j + offset_j\n",
    "                if 0 <= next_i < m and 0 <= next_j < n:\n",
    "                    if grid[next_i][next_j] != grid[i][j]:\n",
    "                        if grid[next_i][next_j] == '0':\n",
    "                            zero_neighbour = True\n",
    "                        continue\n",
    "                    if used[next_i][next_j]:\n",
    "                        continue\n",
    "                    \n",
    "                    sub_cnt, flag = dfs(next_i, next_j)\n",
    "                    ret_cnt += sub_cnt\n",
    "                    if not flag:\n",
    "                        zero_neighbour = True\n",
    "            return ret_cnt, not zero_neighbour\n",
    "        \n",
    "        max_cnt = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if not used[i][j]:\n",
    "                    cnt, flag = dfs(i, j)\n",
    "                    if flag and cnt > max_cnt:\n",
    "                        max_cnt = cnt\n",
    "        return max_cnt\n",
    "\n",
    "\n",
    "                    \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def largestArea(self, grid: List[str]) -> int:\n",
    "        n = len(grid) \n",
    "        if n == 0:\n",
    "            return 0\n",
    "        m = len(grid[0])\n",
    "        if m == 0:\n",
    "            return 0\n",
    "\n",
    "        covered = []\n",
    "        for i in range(n):\n",
    "            covered.append([0] * m)\n",
    "        \n",
    "        def explore(x: int, y: int):\n",
    "            covered[x][y] = 1\n",
    "            area_size = 1\n",
    "            connected = False\n",
    "            if x == 0 or x == n - 1 or y == 0 or y == m - 1:\n",
    "                connected = True\n",
    "            directions = [[-1, 0], [0, -1], [1, 0], [0, 1]]\n",
    "            for (dx, dy) in directions:\n",
    "                nx = x + dx\n",
    "                ny = y + dy\n",
    "                if nx >= 0 and nx < n and ny >= 0 and ny < m:\n",
    "                    if grid[nx][ny] == '0':\n",
    "                        connected = True\n",
    "                        continue\n",
    "                    if covered[nx][ny] == 0 and grid[x][y] == grid[nx][ny]:\n",
    "                        na, nc = explore(nx, ny)\n",
    "                        area_size += na\n",
    "                        connected = connected or nc\n",
    "            return area_size, connected\n",
    "        \n",
    "        ret = 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if covered[i][j] == 0 and grid[i][j] != '0':\n",
    "                    area_size, connected = explore(i, j)\n",
    "                    if not connected and area_size > ret:\n",
    "                        ret = area_size\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def largestArea(self, grid: List[str]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        vis=[[False]*n for _ in range(m)]\n",
    "        ans=0\n",
    "        dix=[(0,1),(0,-1),(1,0),(-1,0)]\n",
    "        def dfs(i,j,s):\n",
    "            vis[i][j]=True\n",
    "            res=1\n",
    "            for dx,dy in dix:\n",
    "                if 0<=i+dx<m and 0<=j+dy<n:\n",
    "                    if vis[i+dx][j+dy]:continue\n",
    "                    if grid[i+dx][j+dy]==s:\n",
    "                        res+=dfs(i+dx, j+dy, s)\n",
    "                    elif grid[i+dx][j+dy]=='0':\n",
    "                        res+=-inf\n",
    "                    else:\n",
    "                        pass\n",
    "                else:\n",
    "                    res+=-inf\n",
    "            return res\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if vis[i][j] or grid[i][j]=='0':\n",
    "                    continue\n",
    "                t=dfs(i,j, grid[i][j])\n",
    "                print(t)\n",
    "                ans=max(ans, t)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def largestArea(self, grid: List[str]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        vis=[[False]*n for _ in range(m)]\n",
    "        ans=0\n",
    "        dix=[(0,1),(0,-1),(1,0),(-1,0)]\n",
    "        def dfs(i,j,s):\n",
    "            vis[i][j]=True\n",
    "            res=1\n",
    "            for dx,dy in dix:\n",
    "                if 0<=i+dx<m and 0<=j+dy<n:\n",
    "                    if vis[i+dx][j+dy]:continue\n",
    "                    if grid[i+dx][j+dy]==s:\n",
    "                        res+=dfs(i+dx, j+dy, s)\n",
    "                    elif grid[i+dx][j+dy]=='0':\n",
    "                        res+=-inf\n",
    "                    else:\n",
    "                        pass\n",
    "                else:\n",
    "                    res+=-inf\n",
    "            return res\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if vis[i][j] or grid[i][j]=='0':\n",
    "                    continue\n",
    "                t=dfs(i,j, grid[i][j])\n",
    "                print(t)\n",
    "                ans=max(ans, t)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def largestArea(self, grid: List[str]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        vis=[[False]*n for _ in range(m)]\n",
    "        ans=0\n",
    "        dix=[(0,1),(0,-1),(1,0),(-1,0)]\n",
    "        def dfs(i,j,s):\n",
    "            vis[i][j]=True\n",
    "            res=1\n",
    "            for dx,dy in dix:\n",
    "                if 0<=i+dx<m and 0<=j+dy<n:\n",
    "                    if vis[i+dx][j+dy]:continue\n",
    "                    if grid[i+dx][j+dy]==s:\n",
    "                        res+=dfs(i+dx, j+dy, s)\n",
    "                    elif grid[i+dx][j+dy]=='0':\n",
    "                        res+=-inf\n",
    "                    else:\n",
    "                        pass\n",
    "                else:\n",
    "                    res+=-inf\n",
    "            return res\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if vis[i][j] or grid[i][j]=='0':\n",
    "                    continue\n",
    "                t=dfs(i,j, grid[i][j])\n",
    "                print(t)\n",
    "                ans=max(ans, t)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestArea(self, grid: List[str]) -> int:\n",
    "        \n",
    "        m, n = len(grid), len(grid[0])\n",
    "        visited = [[False for _ in range(n)] for _ in range(m)]\n",
    "        ans = 0\n",
    "        dix = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "        def dfs(i, j, s):\n",
    "            visited[i][j] = True\n",
    "            res = 1\n",
    "            for dx, dy in dix:\n",
    "                if 0 <= i + dx < m and 0 <= j + dy <n:\n",
    "                    if visited[i + dx][j + dy]:\n",
    "                        continue\n",
    "                    if grid[i + dx][j + dy] == s:\n",
    "                        res += dfs(i + dx, j + dy, s)\n",
    "                    elif grid[i + dx][j + dy] == '0':\n",
    "                        res += -inf\n",
    "                    else:\n",
    "                        pass\n",
    "                else:\n",
    "                    res += -inf\n",
    "            return res\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if visited[i][j] or grid[i][j] == '0':\n",
    "                    continue\n",
    "                t = dfs(i, j, grid[i][j])\n",
    "                ans = max(ans, t)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "class Solution:\n",
    "    def largestArea(self, grid: List[str]) -> int:\n",
    "        res = 0\n",
    "        x = len(grid)\n",
    "        y = len(grid[0])\n",
    "        for i in range(x):\n",
    "            grid[i] = list(grid[i])\n",
    "\n",
    "        tmp = str(list(range(1, 6)))\n",
    "        #tmp = set(range(1, 6))\n",
    "\n",
    "        #print(tmp)\n",
    "        #print(tmp[0])\n",
    "        #print(\"变量类型%s\" %type(tmp))\n",
    "        #print(\"变量类型%s\" %type(tmp[0]))\n",
    "\n",
    "        for i in range(x):\n",
    "            for j in range(y):\n",
    "                if grid[i][j] in tmp:\n",
    "                    flag = 0\n",
    "                    theme = grid[i][j]\n",
    "                    #print(\"theme:%s\" %theme)\n",
    "                    cnt = 0\n",
    "\n",
    "                    queue = deque([(i, j)])\n",
    "                    grid[i][j] = str(int(theme) + 5)\n",
    "                    while queue:\n",
    "                        xTmp, yTmp = queue.popleft()\n",
    "                        cnt += 1\n",
    "                        #print(\"grid[%d][%d]:%s, cnt:%d\" %(xTmp, yTmp, grid[xTmp][yTmp], cnt))\n",
    "\n",
    "                        for ii, jj in [(xTmp, yTmp + 1), (xTmp, yTmp - 1), (xTmp + 1, yTmp), (xTmp - 1, yTmp)]:\n",
    "                            if xTmp == 0 or xTmp == x - 1 or yTmp == 0 or yTmp == y - 1 or (0 <= ii < x and 0 <= jj < y and grid[ii][jj] == '0'):\n",
    "                                flag = 1\n",
    "                                #print(\"flag:%d\" %flag)\n",
    "\n",
    "                        for ii, jj in [(xTmp, yTmp + 1), (xTmp, yTmp - 1), (xTmp + 1, yTmp), (xTmp - 1, yTmp)]:\n",
    "                            if 0 <= ii < x and 0 <= jj < y and grid[ii][jj] == theme:\n",
    "                                queue.append((ii, jj))\n",
    "                                grid[ii][jj] = str(int(theme) + 5)\n",
    "                    if flag == 1:\n",
    "                        cnt = 0\n",
    "                    res = max(res, cnt)\n",
    "                    #print(\"res:%d\" %res)\n",
    "        return res\n",
    "'''\n",
    "                \n",
    "\n",
    "class Solution:\n",
    "    def largestArea(self, grid: List[str]) -> int:\n",
    "        class UnionFind:\n",
    "            def __init__(self, m, n):\n",
    "                self.parent = list(range(m*n))\n",
    "                self.rank = [1]*(m*n)\n",
    "            def find(self, index):\n",
    "                if self.parent[index] != index:\n",
    "                    self.parent[index] = self.find(self.parent[index])\n",
    "                return self.parent[index]\n",
    "            def union(self, i, j):\n",
    "                pi, pj = self.find(i), self.find(j)\n",
    "                if pi == pj:\n",
    "                    return\n",
    "                if self.rank[pj] > self.rank[pi]:\n",
    "                    pi, pj = pj, pi \n",
    "                self.parent[pj] = pi\n",
    "                self.rank[pi] += self.rank[pj]\n",
    "                self.rank[pj] = 0\n",
    "        m = len(grid)\n",
    "        if m < 2:\n",
    "            return 0\n",
    "        n = len(grid[0])\n",
    "        un = UnionFind(m, n)\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] != '0':\n",
    "                    for x, y in [[i,j-1],[i-1,j]]:\n",
    "                        if not(0 <= x < m and 0 <= y < n) or grid[x][y] != grid[i][j]:\n",
    "                            continue\n",
    "                        un.union(i*n+j, x*n+y)\n",
    "                else:\n",
    "                    un.rank[i*n+j] = 0\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == '0':\n",
    "                    for x,y in [[i+1,j],[i-1,j],[i,j+1],[i,j-1]]:\n",
    "                        if not(0 <= x < m and 0 <= y < n) or grid[x][y] == '0':\n",
    "                            continue\n",
    "                        un.rank[un.find(x*n+y)] = 0\n",
    "                elif i == 0 or i == m-1 or j == 0 or j == n-1:\n",
    "                    un.rank[un.find(i*n+j)] = 0\n",
    "        return max(un.rank)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestArea(self, grid: List[str]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        q, head = [], -1\n",
    "        visited = [[False] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            if not visited[i][0]:\n",
    "                q.append([i, 0])\n",
    "                visited[i][0] = True\n",
    "            if not visited[i][n - 1]:\n",
    "                q.append([i, n - 1])\n",
    "                visited[i][n - 1] = True\n",
    "        for j in range(n):\n",
    "            if not visited[0][j]:\n",
    "                q.append([0, j])\n",
    "                visited[0][j] = True\n",
    "            if not visited[m - 1][j]:\n",
    "                q.append([m - 1, j])\n",
    "                visited[m - 1][j] = True\n",
    "        dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == \"0\":\n",
    "                    for d in dirs:\n",
    "                        x, y = i + d[0], j + d[1]\n",
    "                        if x < 0 or x >= m or y < 0 or y >= n:\n",
    "                            continue\n",
    "                        if grid[x][y] == \"0\" or visited[x][y]:\n",
    "                            continue\n",
    "                        q.append([x, y])\n",
    "                        visited[x][y] = True\n",
    "        while head + 1 < len(q):\n",
    "            head += 1\n",
    "            x, y = q[head]\n",
    "            for d in dirs:\n",
    "                xx, yy = x + d[0], y + d[1]\n",
    "                if xx < 0 or xx >= m or yy < 0 or yy >= n:\n",
    "                    continue\n",
    "                if grid[xx][yy] != grid[x][y] or visited[xx][yy]:\n",
    "                    continue\n",
    "                q.append([xx, yy])\n",
    "                visited[xx][yy] = True\n",
    "        max_area = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if visited[i][j] or grid[i][j] == \"0\":\n",
    "                    continue\n",
    "                q, head = [[i, j]], -1\n",
    "                visited[i][j] = True\n",
    "                while head + 1 < len(q):\n",
    "                    head += 1\n",
    "                    x, y = q[head]\n",
    "                    for d in dirs:\n",
    "                        xx, yy = x + d[0], y + d[1]\n",
    "                        if xx < 0 or xx >= m or yy < 0 or yy >= n:\n",
    "                            continue\n",
    "                        if grid[xx][yy] != grid[x][y] or visited[xx][yy]:\n",
    "                            continue\n",
    "                        q.append([xx, yy])\n",
    "                        visited[xx][yy] = True\n",
    "                max_area = max(max_area, len(q))\n",
    "        return max_area"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestArea(self, grid: List[str]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        p = [i for i in range(m * n + 1)]\n",
    "        END = m * n\n",
    "        \n",
    "        def find(x):\n",
    "            while x != p[x]:\n",
    "                p[x] = x = p[p[x]]\n",
    "            return x\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if not i or not j or i == m - 1 or j == n - 1 or grid[i][j] == \"0\":\n",
    "                    p[find(i * n + j)] = END\n",
    "                else:\n",
    "                    idx = find(i * n + j)\n",
    "                    for dx, dy in ((-1, 0), (1, 0), (0, 1), (0, -1)):\n",
    "                        x, y = i + dx, j + dy\n",
    "                        if 0 <= x < m and 0 <= y < n and (grid[i][j] == grid[x][y] or grid[x][y] == \"0\"):\n",
    "                            p[find(x * n + y)] = idx\n",
    "        book = Counter(map(find, p))\n",
    "        book[find(END)] = 0\n",
    "        return max(book.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestArea(self, grid: List[str]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        p = [i for i in range(m * n + 1)]\n",
    "        END = m * n\n",
    "        \n",
    "        def find(x):\n",
    "            while x != p[x]:\n",
    "                p[x] = x = p[p[x]]\n",
    "            return x\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i in (0, m - 1) or j in  (0, n - 1) or grid[i][j] == \"0\":\n",
    "                    p[find(i * n + j)] = END\n",
    "                else:\n",
    "                    idx = find(i * n + j)\n",
    "                    for dx, dy in ((-1, 0), (1, 0), (0, 1), (0, -1)):\n",
    "                        x, y = i + dx, j + dy\n",
    "                        if 0 <= x < m and 0 <= y < n:\n",
    "                            if grid[x][y] == \"0\":\n",
    "                                p[idx] = END\n",
    "                                break\n",
    "                            if grid[i][j] == grid[x][y]:\n",
    "                                p[find(x * n + y)] = idx\n",
    "        book = Counter(map(find, p))\n",
    "        book[find(END)] = 0\n",
    "        return max(book.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestArea(self, grid: List[str]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        p = [i for i in range(m * n + 1)]\n",
    "        END = m * n\n",
    "        \n",
    "        def find(x):\n",
    "            while x != p[x]:\n",
    "                p[x] = x = p[p[x]]\n",
    "            return x\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if not i or not j or i == m - 1 or j == n - 1 or grid[i][j] == \"0\":\n",
    "                    p[find(i * n + j)] = END\n",
    "                else:\n",
    "                    idx = find(i * n + j)\n",
    "                    for dx, dy in ((-1, 0), (1, 0), (0, 1), (0, -1)):\n",
    "                        x, y = i + dx, j + dy\n",
    "                        if 0 <= x < m and 0 <= y < n:\n",
    "                            if grid[x][y] == \"0\":\n",
    "                                p[idx] = END\n",
    "                                break\n",
    "                            if grid[i][j] == grid[x][y]:\n",
    "                                p[find(x * n + y)] = idx\n",
    "        book = Counter(map(find, p))\n",
    "        book[find(END)] = 0\n",
    "        return max(book.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestArea(self, grid: List[str]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        p = [i for i in range(m * n + 1)]\n",
    "        END = m * n\n",
    "        \n",
    "        def find(x):\n",
    "            while x != p[x]:\n",
    "                p[x] = x = p[p[x]]\n",
    "            return x\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                idx = find(i * n + j)\n",
    "                if not i or not j or i == m - 1 or j == n - 1 or grid[i][j] == \"0\":\n",
    "                    p[idx] = END\n",
    "                else:\n",
    "                    for dx, dy in ((-1, 0), (1, 0), (0, 1), (0, -1)):\n",
    "                        x, y = i + dx, j + dy\n",
    "                        if 0 <= x < m and 0 <= y < n:\n",
    "                            if grid[x][y] == \"0\":\n",
    "                                p[idx] = END\n",
    "                                break\n",
    "                            if grid[i][j] == grid[x][y]:\n",
    "                                p[find(x * n + y)] = idx\n",
    "        book = Counter(map(find, p))\n",
    "        book[find(END)] = 0\n",
    "        return max(book.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestArea(self, grid: List[str]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        p = [i for i in range(m * n + 1)]\n",
    "        END = m * n\n",
    "        \n",
    "        def find(x):\n",
    "            while x != p[x]:\n",
    "                p[x] = x = p[p[x]]\n",
    "            return x\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i in (0, m - 1) or j in  (0, n - 1) or grid[i][j] == \"0\":\n",
    "                    p[find(i * n + j)] = END\n",
    "                else:\n",
    "                    idx = find(i * n + j)\n",
    "                    for dx, dy in ((-1, 0), (1, 0), (0, 1), (0, -1)):\n",
    "                        x, y = i + dx, j + dy\n",
    "                        if 0 <= x < m and 0 <= y < n:\n",
    "                            if grid[x][y] == \"0\":\n",
    "                                p[idx] = END\n",
    "                                break\n",
    "                            if grid[i][j] == grid[x][y]:\n",
    "                                p[find(x * n + y)] = idx\n",
    "        book = Counter(map(find, p))\n",
    "        book[find(END)] = 0\n",
    "        return max(book.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestArea(self, grid: List[str]) -> int:\n",
    "        res = 0\n",
    "        x = len(grid)\n",
    "        y = len(grid[0])\n",
    "        for i in range(x):\n",
    "            grid[i] = list(grid[i])\n",
    "\n",
    "        tmp = str(list(range(1, 6)))\n",
    "        #tmp = set(range(1, 6))\n",
    "\n",
    "        print(tmp)\n",
    "        #print(tmp[0])\n",
    "        #print(\"变量类型%s\" %type(tmp))\n",
    "        #print(\"变量类型%s\" %type(tmp[0]))\n",
    "\n",
    "        for i in range(x):\n",
    "            for j in range(y):\n",
    "                if grid[i][j] in tmp:\n",
    "                    flag = 0\n",
    "                    theme = grid[i][j]\n",
    "                    #print(\"theme:%s\" %theme)\n",
    "                    cnt = 0\n",
    "\n",
    "                    queue = deque([(i, j)])\n",
    "                    grid[i][j] = str(int(theme) + 5)\n",
    "                    while queue:\n",
    "                        xTmp, yTmp = queue.popleft()\n",
    "                        cnt += 1\n",
    "                        #print(\"grid[%d][%d]:%s, cnt:%d\" %(xTmp, yTmp, grid[xTmp][yTmp], cnt))\n",
    "\n",
    "                        for ii, jj in [(xTmp, yTmp + 1), (xTmp, yTmp - 1), (xTmp + 1, yTmp), (xTmp - 1, yTmp)]:\n",
    "                            if xTmp == 0 or xTmp == x - 1 or yTmp == 0 or yTmp == y - 1 or (0 <= ii < x and 0 <= jj < y and grid[ii][jj] == '0'):\n",
    "                                flag = 1\n",
    "                                #print(\"flag:%d\" %flag)\n",
    "\n",
    "                        for ii, jj in [(xTmp, yTmp + 1), (xTmp, yTmp - 1), (xTmp + 1, yTmp), (xTmp - 1, yTmp)]:\n",
    "                            if 0 <= ii < x and 0 <= jj < y and grid[ii][jj] == theme:\n",
    "                                queue.append((ii, jj))\n",
    "                                grid[ii][jj] = str(int(theme) + 5)\n",
    "                    if flag == 1:\n",
    "                        cnt = 0\n",
    "                    res = max(res, cnt)\n",
    "                    #print(\"res:%d\" %res)\n",
    "        return res\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestArea(self, grid: List[str]) -> int:\n",
    "        res = 0\n",
    "        x = len(grid)\n",
    "        y = len(grid[0])\n",
    "        for i in range(x):\n",
    "            grid[i] = list(grid[i])\n",
    "\n",
    "        tmp = str(list(range(1, 6)))\n",
    "        #tmp = set(range(1, 6))\n",
    "\n",
    "        print(tmp)\n",
    "        #print(tmp[0])\n",
    "        #print(\"变量类型%s\" %type(tmp))\n",
    "        #print(\"变量类型%s\" %type(tmp[0]))\n",
    "\n",
    "        for i in range(x):\n",
    "            for j in range(y):\n",
    "                if grid[i][j] in tmp:\n",
    "                    flag = 0\n",
    "                    theme = grid[i][j]\n",
    "                    #print(\"theme:%s\" %theme)\n",
    "                    cnt = 0\n",
    "\n",
    "                    queue = deque([(i, j)])\n",
    "                    grid[i][j] = str(int(theme) + 5)\n",
    "                    while queue:\n",
    "                        xTmp, yTmp = queue.popleft()\n",
    "                        cnt += 1\n",
    "                        #print(\"grid[%d][%d]:%s, cnt:%d\" %(xTmp, yTmp, grid[xTmp][yTmp], cnt))\n",
    "\n",
    "                        for ii, jj in [(xTmp, yTmp + 1), (xTmp, yTmp - 1), (xTmp + 1, yTmp), (xTmp - 1, yTmp)]:\n",
    "                            if xTmp == 0 or xTmp == x - 1 or yTmp == 0 or yTmp == y - 1 or (0 <= ii < x and 0 <= jj < y and grid[ii][jj] == '0'):\n",
    "                                flag = 1\n",
    "                                #print(\"flag:%d\" %flag)\n",
    "\n",
    "                        for ii, jj in [(xTmp, yTmp + 1), (xTmp, yTmp - 1), (xTmp + 1, yTmp), (xTmp - 1, yTmp)]:\n",
    "                            if 0 <= ii < x and 0 <= jj < y and grid[ii][jj] == theme:\n",
    "                                queue.append((ii, jj))\n",
    "                                grid[ii][jj] = str(int(theme) + 5)\n",
    "                    if flag == 1:\n",
    "                        cnt = 0\n",
    "                    res = max(res, cnt)\n",
    "                    #print(\"res:%d\" %res)\n",
    "        return res\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestArea(self, grid: List[str]) -> int:\n",
    "        def in_border(i, j):\n",
    "            if i in (0, n - 1) or j in (0, m - 1): return True\n",
    "            for ni, nj in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):\n",
    "                if 0 <= ni < n and 0 <= nj < m and g[ni][nj] == '0':\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        def dfs(i, j):\n",
    "            nonlocal ok\n",
    "            if in_border(i, j): ok = False\n",
    "            vis[i][j] = 1\n",
    "            ans = 1\n",
    "            for ni, nj in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):\n",
    "                if 0 <= ni < n and 0 <= nj < m and g[ni][nj] == g[i][j] and not vis[ni][nj]:\n",
    "                    ans += dfs(ni, nj)\n",
    "            return ans\n",
    "\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        g = [list(x) for x in grid]\n",
    "        vis = [[0] * m for _ in range(n)]\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if g[i][j] != '0' and not vis[i][j]:\n",
    "                    ok = True\n",
    "                    cnt = dfs(i, j)\n",
    "                    if ok: ans = max(ans, cnt)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestArea(self, grid):\n",
    "        def str_to_list(grid):\n",
    "            grid_ls = []\n",
    "            for i in grid:\n",
    "                grid_ls.append(list(i))\n",
    "            return grid_ls\n",
    "\n",
    "        def jia0(ls):\n",
    "            ls.insert(0,['0' for i in range(m)])\n",
    "            for i in ls:\n",
    "                i.insert(0,'0')\n",
    "                i.append('0')\n",
    "            ls.append(['0' for i in range(m+2)])\n",
    "\n",
    "        def find_topic(grid_ls):\n",
    "            ls =[[0 for j in range(m)]for i in range(n)]\n",
    "            ls1 = []\n",
    "            for i in range(n):\n",
    "                for j in range(m):\n",
    "                    if ls[i][j] == 0:\n",
    "                        if grid_ls[i+1][j+1] != '0':\n",
    "                            if grid_ls[i+1][j+1] != grid_ls[i][j+1] and grid_ls[i+1][j+1] != grid_ls[i+1][j]:\n",
    "                                if grid_ls[i][j+1] != '0' and grid_ls[i+2][j+1] != '0' and grid_ls[i+1][j] != '0' and grid_ls[i+1][j+2] != '0':\n",
    "                                    bool = True\n",
    "                                else:\n",
    "                                    bool = False\n",
    "                                ls1.append([bool,(i,j)])\n",
    "                                ls[i][j] = len(ls1)\n",
    "                            elif grid_ls[i + 1][j + 1] == grid_ls[i][j + 1] == grid_ls[i+1][j]:\n",
    "\n",
    "                                if grid_ls[i+2][j+1] == '0' or grid_ls[i+1][j+2] == '0':\n",
    "                                    ls1[ls[i-1][j]-1][0] = False\n",
    "\n",
    "                                ls1[ls[i-1][j]-1].append((i,j))\n",
    "                                ls[i][j] = ls[i - 1][j]\n",
    "                                if ls[i - 1][j] != ls[i][j-1]:\n",
    "                                    ls1[ls[i - 1][j] - 1][0] = ls1[ls[i - 1][j] - 1][0] and ls1[ls[i][j-1]-1][0]\n",
    "                                    for r in ls1[ls[i][j-1]-1][1:]:\n",
    "                                        ls1[ls[i - 1][j] - 1].append(r)\n",
    "                                        ls[r[0]][r[1]] = ls[i][j]\n",
    "\n",
    "                            elif grid_ls[i+1][j+1] == grid_ls[i][j+1]:\n",
    "\n",
    "                                if grid_ls[i+2][j+1] == '0' or grid_ls[i+1][j] == '0' or grid_ls[i+1][j+2] == '0':\n",
    "                                    ls1[ls[i-1][j]-1][0] = False\n",
    "\n",
    "                                ls1[ls[i-1][j]-1].append((i,j))\n",
    "                                ls[i][j] = ls[i-1][j]\n",
    "                            else:\n",
    "                                if grid_ls[i+2][j+1] == '0' or grid_ls[i][j+1] == '0' or grid_ls[i+1][j+2] == '0':\n",
    "                                    ls1[ls[i][j-1]-1][0] = False\n",
    "                                ls1[ls[i][j-1]-1].append((i, j))\n",
    "                                ls[i][j] = ls[i][j-1]\n",
    "            return ls1\n",
    "        def find_max(ls1):\n",
    "            num_max = 0\n",
    "            for i in ls1:\n",
    "                if i != [] and i[0] == True:\n",
    "                    if len(i)-1>num_max:\n",
    "                        num_max = len(i)-1\n",
    "            return num_max\n",
    "\n",
    "        n,m=len(grid),len(grid[0])\n",
    "        grid_ls = str_to_list(grid)\n",
    "        jia0(grid_ls)\n",
    "        ls1 = find_topic(grid_ls)\n",
    "        num_max = find_max(ls1)\n",
    "        return num_max\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestArea(self, grid):\n",
    "        def str_to_list(grid):\n",
    "            grid_ls = []\n",
    "            for i in grid:\n",
    "                grid_ls.append(list(i))\n",
    "            return grid_ls\n",
    "\n",
    "        def jia0(ls):\n",
    "            ls.insert(0,['0' for i in range(m)])\n",
    "            for i in ls:\n",
    "                i.insert(0,'0')\n",
    "                i.append('0')\n",
    "            ls.append(['0' for i in range(m+2)])\n",
    "\n",
    "        def find_topic(grid_ls):\n",
    "            ls =[[0 for j in range(m)]for i in range(n)]\n",
    "            ls1 = []\n",
    "            for i in range(n):\n",
    "                for j in range(m):\n",
    "                    if ls[i][j] == 0:\n",
    "                        if grid_ls[i+1][j+1] != '0':\n",
    "                            if grid_ls[i+1][j+1] != grid_ls[i][j+1] and grid_ls[i+1][j+1] != grid_ls[i+1][j]:\n",
    "                                if grid_ls[i][j+1] != '0' and grid_ls[i+2][j+1] != '0' and grid_ls[i+1][j] != '0' and grid_ls[i+1][j+2] != '0':\n",
    "                                    bool = True\n",
    "                                else:\n",
    "                                    bool = False\n",
    "                                ls1.append([bool,(i,j)])\n",
    "                                ls[i][j] = len(ls1)\n",
    "                            elif grid_ls[i + 1][j + 1] == grid_ls[i][j + 1] == grid_ls[i+1][j]:\n",
    "\n",
    "                                if grid_ls[i+2][j+1] == '0' or grid_ls[i+1][j+2] == '0':\n",
    "                                    ls1[ls[i-1][j]-1][0] = False\n",
    "\n",
    "                                ls1[ls[i-1][j]-1].append((i,j))\n",
    "                                ls[i][j] = ls[i - 1][j]\n",
    "                                if ls[i - 1][j] != ls[i][j-1]:\n",
    "                                    ls1[ls[i - 1][j] - 1][0] = ls1[ls[i - 1][j] - 1][0] and ls1[ls[i][j-1]-1][0]\n",
    "                                    for r in ls1[ls[i][j-1]-1][1:]:\n",
    "                                        ls1[ls[i - 1][j] - 1].append(r)\n",
    "                                        ls[r[0]][r[1]] = ls[i][j]\n",
    "\n",
    "                            elif grid_ls[i+1][j+1] == grid_ls[i][j+1]:\n",
    "\n",
    "                                if grid_ls[i+2][j+1] == '0' or grid_ls[i+1][j] == '0' or grid_ls[i+1][j+2] == '0':\n",
    "                                    ls1[ls[i-1][j]-1][0] = False\n",
    "\n",
    "                                ls1[ls[i-1][j]-1].append((i,j))\n",
    "                                ls[i][j] = ls[i-1][j]\n",
    "                            else:\n",
    "                                if grid_ls[i+2][j+1] == '0' or grid_ls[i][j+1] == '0' or grid_ls[i+1][j+2] == '0':\n",
    "                                    ls1[ls[i][j-1]-1][0] = False\n",
    "                                ls1[ls[i][j-1]-1].append((i, j))\n",
    "                                ls[i][j] = ls[i][j-1]\n",
    "            return ls1\n",
    "        def find_max(ls1):\n",
    "            num_max = 0\n",
    "            for i in ls1:\n",
    "                if i != [] and i[0] == True:\n",
    "                    if len(i)-1>num_max:\n",
    "                        num_max = len(i)-1\n",
    "            return num_max\n",
    "\n",
    "        n,m=len(grid),len(grid[0])\n",
    "        grid_ls = str_to_list(grid)\n",
    "        jia0(grid_ls)\n",
    "        ls1 = find_topic(grid_ls)\n",
    "        num_max = find_max(ls1)\n",
    "        return num_max\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class setUnion(object):\n",
    "    def __init__(self,size):\n",
    "        self.parent=list(range(size))\n",
    "        self.rank=[1]*size\n",
    "        self.setCount=size\n",
    "    def find(self,i):\n",
    "        if self.parent[i]==i:\n",
    "            return i\n",
    "        else:\n",
    "            self.parent[i]=self.find(self.parent[i])\n",
    "            return self.parent[i]\n",
    "    def union(self,i,j):\n",
    "        x,y=self.find(i),self.find(j)\n",
    "        if x==y:\n",
    "            return\n",
    "        if self.rank[x]<self.rank[y]:\n",
    "            x,y=y,x\n",
    "        self.rank[x]+=self.rank[y]\n",
    "        self.parent[y]=x\n",
    "        self.setCount-=1\n",
    "    def is_connected(self,i,j):\n",
    "        return self.find(i)==self.find(j)\n",
    "    def get_partset(self):\n",
    "        part=defaultdict(list)\n",
    "        for i in range(len(self.parent)):\n",
    "            part[self.find(i)].append(i)\n",
    "        return part\n",
    "class Solution:\n",
    "    def largestArea(self, grid: List[str]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        for i in range(m):\n",
    "            cur=list(grid[i])\n",
    "            cur=[int(x) for x in cur]\n",
    "            grid[i]=cur\n",
    "        kkk=setUnion(m*n)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                for x,y in [(0,1),(1,0)]:\n",
    "                    new_i,new_j=x+i,y+j\n",
    "                    if 0<=new_i<m and 0<=new_j<n and grid[new_i][new_j]==grid[i][j]:\n",
    "                        kkk.union(i*n+j,new_i*n+new_j)\n",
    "        ans=0\n",
    "        part=kkk.get_partset()\n",
    "        for p in part:\n",
    "            flag=False\n",
    "            for x in part[p]:\n",
    "                i,j=x//n,x%n\n",
    "                for a,b in [(1,0),(0,1),(-1,0),(0,-1)]:\n",
    "                    new_i,new_j=i+a,j+b\n",
    "                    if new_i<0 or new_i>=m or new_j<0 or new_j>=n or grid[new_i][new_j]==0 or grid[i][j]==0:\n",
    "                        flag=True\n",
    "                        break\n",
    "                if flag: break\n",
    "            else: ans=max(ans,len(part[p]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class setUnion(object):\n",
    "    def __init__(self,size):\n",
    "        self.parent=list(range(size))\n",
    "        self.rank=[1]*size\n",
    "        self.setCount=size\n",
    "    def find(self,i):\n",
    "        if self.parent[i]==i:\n",
    "            return i\n",
    "        else:\n",
    "            self.parent[i]=self.find(self.parent[i])\n",
    "            return self.parent[i]\n",
    "    def union(self,i,j):\n",
    "        x,y=self.find(i),self.find(j)\n",
    "        if x==y:\n",
    "            return\n",
    "        if self.rank[x]<self.rank[y]:\n",
    "            x,y=y,x\n",
    "        self.rank[x]+=self.rank[y]\n",
    "        self.parent[y]=x\n",
    "        self.setCount-=1\n",
    "    def is_connected(self,i,j):\n",
    "        return self.find(i)==self.find(j)\n",
    "    def get_partset(self):\n",
    "        part=defaultdict(list)\n",
    "        for i in range(len(self.parent)):\n",
    "            part[self.find(i)].append(i)\n",
    "        return part\n",
    "class Solution:\n",
    "    def largestArea(self, grid: List[str]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        for i in range(m):\n",
    "            cur=list(grid[i])\n",
    "            cur=[int(x) for x in cur]\n",
    "            grid[i]=cur\n",
    "        kkk=setUnion(m*n)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                for x,y in [(0,1),(1,0)]:\n",
    "                    new_i,new_j=x+i,y+j\n",
    "                    if 0<=new_i<m and 0<=new_j<n and grid[new_i][new_j]==grid[i][j]:\n",
    "                        kkk.union(i*n+j,new_i*n+new_j)\n",
    "        ans=0\n",
    "        part=kkk.get_partset()\n",
    "        for p in part:\n",
    "            flag=False\n",
    "            for x in part[p]:\n",
    "                i,j=x//n,x%n\n",
    "                for a,b in [(1,0),(0,1),(-1,0),(0,-1)]:\n",
    "                    new_i,new_j=i+a,j+b\n",
    "                    if new_i<0 or new_i>=m or new_j<0 or new_j>=n or grid[new_i][new_j]==0 or grid[i][j]==0:\n",
    "                        flag=True\n",
    "                        break\n",
    "                if flag: break\n",
    "            else: ans=max(ans,len(part[p]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "'''\n",
    "--- 从此处复制 ---\n",
    "'''\n",
    "class IdentityDefaultDict(defaultdict):\n",
    "    '''\n",
    "    该类用于处理并查集初始化的恒等映射\n",
    "    '''\n",
    "    def __missing__(self, key):\n",
    "        return key\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n=None, m=None):\n",
    "        self.parent = IdentityDefaultDict()\n",
    "        if n: self.parent = list(range(n))\n",
    "        if n and m: \n",
    "            self.parent = [[(i, j) for j in range(m)] for i in range(n)]\n",
    "    def find(self, x):\n",
    "        a, b = x\n",
    "        if self.parent[a][b] != x: self.parent[a][b] = self.find(self.parent[a][b])\n",
    "        return self.parent[a][b]\n",
    "    def merge(self, x, y):\n",
    "        x, y = self.find(x), self.find(y)\n",
    "        if x != y:\n",
    "            a, b = x\n",
    "            self.parent[a][b] = y\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def largestArea(self, grid: List[str]) -> int:\n",
    "        \n",
    "        grid = np.array([[int(y) for y in x] for x in grid])\n",
    "        h, w = grid.shape\n",
    "        uf = UnionFind(h+2, w+2)\n",
    "        mat = np.zeros((h+2, w+2), dtype=int)\n",
    "        mat[1:-1, 1:-1] = grid\n",
    "        grid = mat\n",
    "        for x in range(h+2):\n",
    "            for y in range(w+2):\n",
    "                if grid[x][y] == 0:\n",
    "                    uf.merge((0, 0), (x, y))\n",
    "                    for dx, dy in (0, 1), (1, 0), (0, -1), (-1, 0):\n",
    "                        nx, ny = x + dx, y + dy\n",
    "                        if 0 <= nx < h+2 and 0 <= ny < w+2:\n",
    "                            uf.merge((x, y), (nx, ny))\n",
    "                else:\n",
    "                    for dx, dy in (0, 1), (1, 0), (0, -1), (-1, 0):\n",
    "                        nx, ny = x + dx, y + dy\n",
    "                        if 0 <= nx < h+2 and 0 <= ny < w+2 and grid[nx][ny] == grid[x][y]:\n",
    "                            uf.merge((x, y), (nx, ny))\n",
    "        # for x in range(1, h+1):\n",
    "        #     for y in range(1, w+1):\n",
    "        #         if uf.find((x, y)) == uf.find((0, 0)):\n",
    "        #             grid[x][y] = 0\n",
    "        # [print(x) for x in grid]\n",
    "        cnts = Counter()\n",
    "        for x in range(1, h+1):\n",
    "            for y in range(1, w+1):\n",
    "                if uf.find((x, y)) != uf.find((0, 0)):\n",
    "                    cnts[uf.find((x, y))] += 1\n",
    "        return max([0] + list(cnts.values()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "'''\n",
    "--- 从此处复制 ---\n",
    "'''\n",
    "class IdentityDefaultDict(defaultdict):\n",
    "    '''\n",
    "    该类用于处理并查集初始化的恒等映射\n",
    "    '''\n",
    "    def __missing__(self, key):\n",
    "        return key\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n=None, m=None):\n",
    "        self.parent = IdentityDefaultDict()\n",
    "        if n: self.parent = list(range(n))\n",
    "        if n and m: \n",
    "            self.parent = [[(i, j) for j in range(m)] for i in range(n)]\n",
    "    def find(self, x):\n",
    "        a, b = x\n",
    "        if self.parent[a][b] != x: self.parent[a][b] = self.find(self.parent[a][b])\n",
    "        return self.parent[a][b]\n",
    "    def merge(self, x, y):\n",
    "        x, y = self.find(x), self.find(y)\n",
    "        if x != y:\n",
    "            a, b = x\n",
    "            self.parent[a][b] = y\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def largestArea(self, grid: List[str]) -> int:\n",
    "        \n",
    "        grid = np.array([[int(y) for y in x] for x in grid])\n",
    "        h, w = grid.shape\n",
    "        uf = UnionFind(h+2, w+2)\n",
    "        mat = np.zeros((h+2, w+2), dtype=int)\n",
    "        mat[1:-1, 1:-1] = grid\n",
    "        grid = mat\n",
    "        for x in range(h+2):\n",
    "            for y in range(w+2):\n",
    "                if grid[x][y] == 0:\n",
    "                    uf.merge((0, 0), (x, y))\n",
    "                    for dx, dy in (0, 1), (1, 0), (0, -1), (-1, 0):\n",
    "                        nx, ny = x + dx, y + dy\n",
    "                        if 0 <= nx < h+2 and 0 <= ny < w+2:\n",
    "                            uf.merge((x, y), (nx, ny))\n",
    "                else:\n",
    "                    for dx, dy in (0, 1), (1, 0), (0, -1), (-1, 0):\n",
    "                        nx, ny = x + dx, y + dy\n",
    "                        if 0 <= nx < h+2 and 0 <= ny < w+2 and grid[nx][ny] == grid[x][y]:\n",
    "                            uf.merge((x, y), (nx, ny))\n",
    "        # for x in range(1, h+1):\n",
    "        #     for y in range(1, w+1):\n",
    "        #         if uf.find((x, y)) == uf.find((0, 0)):\n",
    "        #             grid[x][y] = 0\n",
    "        # [print(x) for x in grid]\n",
    "        cnts = Counter()\n",
    "        for x in range(1, h+1):\n",
    "            for y in range(1, w+1):\n",
    "                if uf.find((x, y)) != uf.find((0, 0)):\n",
    "                    cnts[uf.find((x, y))] += 1\n",
    "        return max([0] + list(cnts.values()))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestArea(self, grid: List[str]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        parent = [i for i in range(m*n)]\n",
    "        info_dict = {}\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                idx = i*n + j\n",
    "                if i== 0 or i== m-1 or j == 0 or j == n-1 or grid[i][j] == '0':\n",
    "                    info_dict[idx] = [1, 1]\n",
    "                else:\n",
    "                    info_dict[idx] = [0, 1]\n",
    "        # info_dict = {i: [1, 1] for i in range(m*n) if i % n == 0 or i % n == n-1 or i // n == 0 or i // n == m-1 or grid[i//n][i%n] == '0' else [0, 1]}\n",
    "        def find(idx):\n",
    "            while parent[idx] != idx:\n",
    "                idx = parent[idx]\n",
    "            \n",
    "            return idx\n",
    "\n",
    "        def union(p, q):\n",
    "            root_p = find(p)\n",
    "            root_q = find(q)\n",
    "            \n",
    "            if root_p != root_q:\n",
    "                parent[root_p] = root_q\n",
    "                info = info_dict.pop(root_p)\n",
    "                info_dict[root_q][1] += info[1]\n",
    "                info_dict[root_q][0] = 1 if info[0] else info_dict[root_q][0]\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):  \n",
    "                idx = i * n + j\n",
    "                if i != 0 :\n",
    "                    if grid[i][j] == grid[i-1][j]:\n",
    "                        upper_idx = (i-1)*n + j\n",
    "                        union(upper_idx,idx)\n",
    "                    elif grid[i-1][j] == '0':\n",
    "                        parent_idx = find(idx)\n",
    "                        info_dict[parent_idx][0] = 1\n",
    "                    elif grid[i][j] == '0':\n",
    "                        upper_idx = (i-1)*n + j\n",
    "                        parent_idx = find(upper_idx)\n",
    "                        info_dict[parent_idx][0] = 1\n",
    "                    \n",
    "                if j != 0:\n",
    "                    if grid[i][j] == grid[i][j-1]:\n",
    "                        left_idx = i*n + j -1\n",
    "                        union(left_idx, idx)\n",
    "                    elif grid[i][j-1] == '0':\n",
    "                        parent_idx = find(idx)\n",
    "                        info_dict[parent_idx][0] = 1\n",
    "                    \n",
    "                    elif grid[i][j] == '0':\n",
    "                        left_idx = i*n + j -1\n",
    "                        parent_idx = find(left_idx)\n",
    "                        info_dict[parent_idx][0] = 1\n",
    "\n",
    "\n",
    "        max_area = 0        \n",
    "        for idx in info_dict:\n",
    "            if info_dict[idx][0] == 0:\n",
    "                max_area = max(max_area, info_dict[idx][1])\n",
    "        \n",
    "\n",
    "        return max_area"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestArea(self, grid: List[str]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        parent = [i for i in range(m*n)]\n",
    "        info_dict = {}\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                idx = i*n + j\n",
    "                if i== 0 or i== m-1 or j == 0 or j == n-1 or grid[i][j] == '0':\n",
    "                    info_dict[idx] = [1, 1]\n",
    "                else:\n",
    "                    info_dict[idx] = [0, 1]\n",
    "        # info_dict = {i: [1, 1] for i in range(m*n) if i % n == 0 or i % n == n-1 or i // n == 0 or i // n == m-1 or grid[i//n][i%n] == '0' else [0, 1]}\n",
    "        def find(idx):\n",
    "            while parent[idx] != idx:\n",
    "                idx = parent[idx]\n",
    "            \n",
    "            return idx\n",
    "\n",
    "        def union(p, q):\n",
    "            root_p = find(p)\n",
    "            root_q = find(q)\n",
    "            \n",
    "            if root_p != root_q:\n",
    "                parent[root_p] = root_q\n",
    "                info = info_dict.pop(root_p)\n",
    "                info_dict[root_q][1] += info[1]\n",
    "                info_dict[root_q][0] = 1 if info[0] else info_dict[root_q][0]\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):  \n",
    "                idx = i * n + j\n",
    "                if i != 0 :\n",
    "                    if grid[i][j] == grid[i-1][j]:\n",
    "                        upper_idx = (i-1)*n + j\n",
    "                        union(upper_idx,idx)\n",
    "                    elif grid[i-1][j] == '0':\n",
    "                        parent_idx = find(idx)\n",
    "                        info_dict[parent_idx][0] = 1\n",
    "                    elif grid[i][j] == '0':\n",
    "                        upper_idx = (i-1)*n + j\n",
    "                        parent_idx = find(upper_idx)\n",
    "                        info_dict[parent_idx][0] = 1\n",
    "                    \n",
    "                if j != 0:\n",
    "                    if grid[i][j] == grid[i][j-1]:\n",
    "                        left_idx = i*n + j -1\n",
    "                        union(left_idx, idx)\n",
    "                    elif grid[i][j-1] == '0':\n",
    "                        parent_idx = find(idx)\n",
    "                        info_dict[parent_idx][0] = 1\n",
    "                    \n",
    "                    elif grid[i][j] == '0':\n",
    "                        left_idx = i*n + j -1\n",
    "                        parent_idx = find(left_idx)\n",
    "                        info_dict[parent_idx][0] = 1\n",
    "\n",
    "\n",
    "        max_area = 0        \n",
    "        for idx in info_dict:\n",
    "            if info_dict[idx][0] == 0:\n",
    "                max_area = max(max_area, info_dict[idx][1])\n",
    "        \n",
    "\n",
    "        return max_area"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestArea(self, grid: List[str]) -> int:\n",
    "        rows=len(grid)\n",
    "        cols=len(grid[0])\n",
    "        fa=list(range(rows*cols))\n",
    "        def find(x):\n",
    "            if fa[x]==x:\n",
    "                return x\n",
    "            fa[x]=find(fa[x])\n",
    "            return fa[x]\n",
    "        def legal(x,y):\n",
    "            return x>=0 and y>=0 and x<rows and y<cols\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                for dx,dy in ((0,1),(0,-1),(-1,0),(1,0)):\n",
    "                    x,y=i+dx,j+dy\n",
    "                    if legal(x,y) and grid[x][y]==grid[i][j]:\n",
    "                        m=i*cols+j\n",
    "                        n=x*cols+y\n",
    "                        fm=find(m)\n",
    "                        fn=find(n)\n",
    "                        if fm!=fn:\n",
    "                            fa[fm]=fa[fn]\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                x=i*cols+j\n",
    "                fa[x]=find(x)\n",
    "        bad={}\n",
    "        for i in range(rows):\n",
    "            x=i*cols\n",
    "            bad[fa[x]]=1\n",
    "            x=i*cols+cols-1\n",
    "            bad[fa[x]]=1\n",
    "        for i in range(cols):\n",
    "            x=i\n",
    "            bad[fa[x]]=1\n",
    "            x=(rows-1)*cols+i\n",
    "            bad[fa[x]]=1\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                if grid[i][j]=='0':\n",
    "                    bad[fa[i*cols+j]]=1\n",
    "                    for dx,dy in ((0,1),(0,-1),(-1,0),(1,0)):\n",
    "                        x,y=i+dx,j+dy\n",
    "                        if legal(x,y):\n",
    "                            p=x*cols+y\n",
    "                            bad[fa[p]]=1\n",
    "        from collections import Counter\n",
    "        fac=Counter(fa)\n",
    "        ans=0\n",
    "        for k,v in fac.items():\n",
    "            if k not in bad:\n",
    "                ans=max(ans,v)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestArea(self, grid: List[str]) -> int:\n",
    "\n",
    "        ans = 0\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        next = [\n",
    "            [0, 1],\n",
    "            [1, 0],\n",
    "            [0, -1],\n",
    "            [-1, 0]\n",
    "        ]\n",
    "        visited = set()\n",
    "      \n",
    "        # 初始化每个位置是否可以到达edge\n",
    "        grid_connect_edge = [[False for _ in range(n)] for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i in [0, m - 1] or j in [0, n - 1]:  # 四周都conncted edge\n",
    "                    grid_connect_edge[i][j] = True\n",
    "                else:\n",
    "                    for k in range(4):  # 4个方向有0，就conncted edge\n",
    "                        ti = i + next[k][0]\n",
    "                        tj = j + next[k][1]\n",
    "                        if 0 <= ti < m and 0 <= tj < n and grid[ti][tj] == \"0\":\n",
    "                            grid_connect_edge[i][j] = True\n",
    "                            break\n",
    "\n",
    "        def dfs(x, y):\n",
    "            self.current_cnt += 1\n",
    "            visited.add((x, y))\n",
    "\n",
    "            if grid_connect_edge[x][y] is True:\n",
    "                self.is_connect_border = True\n",
    "\n",
    "            for k in range(4):\n",
    "                tx = x + next[k][0]\n",
    "                ty = y + next[k][1]\n",
    "                if 0 <= tx < m and 0 <= ty < n and grid[tx][ty] == grid[x][y] and (tx, ty) not in visited:\n",
    "                    dfs(tx, ty)\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] != \"0\" and (i, j) not in visited:\n",
    "                    self.is_connect_border = False  # flag if can connected edge\n",
    "                    self.current_cnt = 0  # record the maximum area\n",
    "\n",
    "                    dfs(i, j)\n",
    "                    \n",
    "                    if self.is_connect_border is False:  # if cannot, update answer\n",
    "                        ans = max(ans, self.current_cnt)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestArea(self, grid: List[str]) -> int:\n",
    "\n",
    "        ans = 0\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        next = [\n",
    "            [0, 1],\n",
    "            [1, 0],\n",
    "            [0, -1],\n",
    "            [-1, 0]\n",
    "        ]\n",
    "        visited = set()\n",
    "      \n",
    "        # 初始化每个位置是否可以到达edge\n",
    "        grid_connect_edge = [[False for _ in range(n)] for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i in [0, m - 1] or j in [0, n - 1]:\n",
    "                    grid_connect_edge[i][j] = True\n",
    "                else:\n",
    "                    for k in range(4):  # 4个方向有0，就conncted edge\n",
    "                        ti = i + next[k][0]\n",
    "                        tj = j + next[k][1]\n",
    "                        if 0 <= ti < m and 0 <= tj < n and grid[ti][tj] == \"0\":\n",
    "                            grid_connect_edge[i][j] = True\n",
    "                            break\n",
    "\n",
    "        def dfs(x, y):\n",
    "            self.current_cnt += 1\n",
    "            visited.add((x, y))\n",
    "\n",
    "            if grid_connect_edge[x][y] is True:\n",
    "                self.is_connect_border = True\n",
    "\n",
    "            for k in range(4):\n",
    "                tx = x + next[k][0]\n",
    "                ty = y + next[k][1]\n",
    "                if 0 <= tx < m and 0 <= ty < n and grid[tx][ty] == grid[x][y] and (tx, ty) not in visited:\n",
    "                    dfs(tx, ty)\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] != \"0\" and (i, j) not in visited:\n",
    "                    self.is_connect_border = False\n",
    "                    self.current_cnt = 0\n",
    "\n",
    "                    dfs(i, j)\n",
    "                    \n",
    "                    if self.is_connect_border is False:\n",
    "                        ans = max(ans, self.current_cnt)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    # def largestArea(self, grid: List[str]) -> int:\n",
    "    #   ans = 0\n",
    "\n",
    "    #   next = [\n",
    "    #     [0, 1],\n",
    "    #     [1, 0],\n",
    "    #     [0, -1],\n",
    "    #     [-1, 0]\n",
    "    #   ]\n",
    "    #   m, n = len(grid), len(grid[0])\n",
    "    #   visited = set()\n",
    "    #   all_edge_0 = set()  # 记录所有从边界能到达的空间位置\n",
    "    #   book = [[0 for _ in range(n)] for _ in range(m)]\n",
    "\n",
    "    #   def find_all_edge_0(x, y):\n",
    "    #     book[x][y] = 1\n",
    "    #     all_edge_0.add((x, y))\n",
    "    #     # print(x, y)\n",
    "\n",
    "    #     for k in range(4):\n",
    "    #       tx = x + next[k][0]\n",
    "    #       ty = y + next[k][1]\n",
    "    #       if 0 <= tx < m and 0 <= ty < n and grid[tx][ty] == \"0\" and book[tx][ty] == 0:\n",
    "    #         find_all_edge_0(tx, ty)\n",
    "\n",
    "    #   for i in [0, m-1]:\n",
    "    #     for j in range(n):\n",
    "    #       if grid[i][j] == \"0\":\n",
    "    #         find_all_edge_0(i, j)\n",
    "    #   for i in range(m):\n",
    "    #     for j in [0, n-1]:\n",
    "    #       if grid[i][j] == \"0\":\n",
    "    #         find_all_edge_0(i, j)\n",
    "    #   print(all_edge_0)\n",
    "\n",
    "    #   def dfs(x, y):\n",
    "    #     self.current_cnt += 1\n",
    "    #     visited.add((x, y))\n",
    "\n",
    "    #     if x in [0, m - 1] or y in [0, n - 1]:\n",
    "    #       # print((x, y, tx, ty), '-=', tx in [0, m - 1], ty in [0, n - 1], (tx, ty) in all_edge_0)\n",
    "    #       self.is_connect_border = True\n",
    "\n",
    "    #     for k in range(4):\n",
    "    #       tx = x + next[k][0]\n",
    "    #       ty = y + next[k][1]\n",
    "    #       if (tx, ty) in all_edge_0:\n",
    "    #         print((x, y, tx, ty), '-=', tx in [0, m - 1], ty in [0, n - 1], (tx, ty) in all_edge_0)\n",
    "    #         self.is_connect_border = True\n",
    "    #       if 0 <= tx < m and 0 <= ty < n and grid[tx][ty] == grid[x][y] and (tx, ty) not in visited:\n",
    "    #           dfs(tx, ty)\n",
    "\n",
    "    #   for i in range(m):\n",
    "    #     for j in range(n):\n",
    "    #       if grid[i][j] != \"0\" and (i, j) not in visited:\n",
    "    #         self.is_connect_border = False\n",
    "    #         self.current_cnt = 0\n",
    "\n",
    "    #         dfs(i, j)\n",
    "    #         # print(i, j, self.is_connect_border)\n",
    "    #         if self.is_connect_border is False:\n",
    "    #           ans = max(ans, self.current_cnt)\n",
    "    #   return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestArea(self, grid: List[str]) -> int:\n",
    "        def g(i,j,pr):\n",
    "            if not(0<=i<n and 0<=j<m) or grid[i][j]=='0':\n",
    "                return False\n",
    "            if grid[i][j]!=pr:\n",
    "                return True\n",
    "            v[(i,j)]+=1\n",
    "            res=True\n",
    "            for a,b in [[0,1],[0,-1],[1,0],[-1,0]]:\n",
    "                if (i+a,j+b) not in v:\n",
    "                   res=min(g(i+a,j+b,pr),res)\n",
    "            return res\n",
    "        v,n,m=Counter(),len(grid),len(grid[0])\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j]=='0':\n",
    "                    continue\n",
    "                if (i,j) not in v:\n",
    "                  r=len(v)\n",
    "                  if g(i,j,grid[i][j]):\n",
    "                     ans=max(ans,len(v)-r)\n",
    "        return ans              \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
